package Test_1203;

import java.util.Arrays;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
//堆的创建
public class Heap {
    //数据，大小；
    public int[] elem;
    public int usedSize;
    public Heap(int[] elem) {
        this.elem = elem;
    }
    //初始化
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            //大小增加
            usedSize++;
        }
    }
    //创建大堆:将父节点向下调整
    public void creatHeap(){
          //从最后一个父节点开始从下往上将父节点进行向下调整
        for (int parent = (this.usedSize-2)/2; parent >=0; parent--) {
              //将父节点向下调整
            siftDown(parent,this.usedSize);
        }
    }
    /*将子节点中的最大值的子节点与父节点进行比较：
    如果大于父节点进行交换；
    小于则减父节点的下标到下一个*/
    public void siftDown(int parent,int usedSize){
        //子节点：
           int child=parent*2+1;
           while(child<usedSize){
           //比较两个子节点，如果左节点小于右节点，将子节点加加到右节点的下标
           if(child+1<usedSize&&elem[child]<elem[child+1]){
               child++;
           }
           //比较子节点与父节点
        //如果大于交换
        if(elem[child]>elem[parent]){
            swap(elem,child,parent);
        }else{
            //如果小于，说明该子树已经是大堆，不必再交换
            break;
        }
           }
    }
    public void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[j]=tmp;
        tmp=elem[j];
    }
    //堆的插入：将子节点向上调整
    public void offer(int val){
         //看是否已满
        if(isFull()){
            //满了扩容
            this.elem= Arrays.copyOf(elem,2*elem.length);
        }
        //插入在最后一个位置
        elem[usedSize]=val;
        //节点增加
        usedSize++;
        //向上调整
        siftUp(elem[usedSize]);
    }
    public boolean isFull(){
          return this.usedSize==elem.length;
    }
    /*将插入的元素放到最后一个位置，将其与父节点进行比较，
    如果大于父节点进行交换，交换完
    将在该节点与该节点的父节点变为现在的父节点，随后进行比较；
    如果小于父节点结束*/
    public void siftUp(int child){
        //怎么确定父节点是减1还是减2
        int parent=(child-1)/2;
        while(parent>=0){
            //将其与父节点进行比较
            //如果大于父节点进行交换
            if(elem[parent]<elem[child]){
                swap(elem,parent,child);
                //将在该节点与该节点的父节点变为现在的父节点
                parent=(parent-1)/2;
            }else{
                break;
            }
        }
    }
    //删除根节点
    //将根节点的值与最后一个节点进行交换；
    //节点数量减少
    public int poll(){
        if(isEmpty()){
            return -1;

        }
        int val=elem[0];
        swap(elem,0,usedSize-1);
         //进行向下转型来调整根节点
        siftDown(0,this.usedSize-1);
        usedSize--;
        return val;
    }
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    public int  peek(){
        if(isEmpty()){
            return -1;
        }
    return elem[0];
    }
    //堆排序：
   // 将第一个元素与最后一个元素交换，
    //end--；
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
        swap(elem,0,end);
        siftDown(0,usedSize-1);
        end--;
    }}
}
